//
// Created by Administrator on 2021/7/1.
//

#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>> &graph) {
        /**
         * 怎么传递路径信息  还是dfs吧
         */
        return solve(graph, 0);
    }

    /**
     * dfs递归函数
     * @param graph 给出的图
     * @param node  当前的节点
     * @return
     */
    vector<vector<int>> solve(vector<vector<int>> &graph, int node) {
        int N = (int) graph.size();
        vector<vector<int>> ans;
        // 如果到达目标节点,返回一个[N-1]
        if (node == N - 1) {
            ans.emplace_back();
            ans.back().push_back(N - 1);
            return ans;
        }
        // 搜索当前节点的邻节点
        for (auto &neighbor:graph[node]) {
            // path 是各个邻节点到达目标节点的路径
            for (auto &path:solve(graph, neighbor)) {
                // 当前节点塞到最前面
                path.insert(path.begin(), node);
                // 添加了当前节点的路径返回
                ans.push_back(path);
            }
        }
        return ans;
    }


};

class Solution2 { // 优秀题解 回溯
public:
    void dfs(vector<vector<int>> &graph, int pos) {
        if (pos == graph.size() - 1) {
            ans.push_back(res);
            return;
        }
        if (pos == 0)
            res.push_back(0);
        for (auto &x:graph[pos]) {
            res.push_back(x);
            dfs(graph, x);
            res.pop_back();
        }
    }

    vector<vector<int>> allPathsSourceTarget(vector<vector<int>> &graph) {
        dfs(graph, 0);
        return ans;
    }

private:
    vector<vector<int>> ans;
    vector<int> res;
};

int main() {
    vector<vector<int>> graph{{1, 2},
                              {3},
                              {3},
                              {}};
    Solution2 sol;
    auto ans = sol.allPathsSourceTarget(graph);
    for (auto &x:ans) {
        for (auto &y:x) {
            cout << y;
            cout << " ";
        }
        cout << endl;
    }
    return 0;
}